package com.xiyou.week03.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 94. 二叉树的中序遍历
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 *
 * @ClassName：InorderTraversal
 * @Author：西柚
 * @Date：2022/1/13 4:52 下午
 * @Versiion：1.0
 */
public class InorderTraversal {

    List<Integer> seq;

    /**
     * 输入：root = [1,null,2,3]
     * 输出：[1,3,2]
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        seq = new ArrayList<>();

        dfs(root);
        return seq;
    }

    void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        seq.add(root.val);
        dfs(root.right);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
